package com.zjsru.plan2023.other;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Author: cookLee
 * @Date: 2023-11-25
 * 统计和小于目标的下标对数目
 */
public class CountPairs {

    /**
     * 主
     * \
     * 输入：nums = [-1,1,2,3,1], target = 2
     * 输出：3
     * 解释：总共有 3 个下标对满足题目描述：
     * - (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target
     * - (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target
     * - (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target
     * 注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target 。
     * \
     * 输入：nums = [-6,2,5,-2,-7,-1,3], target = -2
     * 输出：10
     * 解释：总共有 10 个下标对满足题目描述：
     * - (0, 1) ，0 < 1 且 nums[0] + nums[1] = -4 < target
     * - (0, 3) ，0 < 3 且 nums[0] + nums[3] = -8 < target
     * - (0, 4) ，0 < 4 且 nums[0] + nums[4] = -13 < target
     * - (0, 5) ，0 < 5 且 nums[0] + nums[5] = -7 < target
     * - (0, 6) ，0 < 6 且 nums[0] + nums[6] = -3 < target
     * - (1, 4) ，1 < 4 且 nums[1] + nums[4] = -5 < target
     * - (3, 4) ，3 < 4 且 nums[3] + nums[4] = -9 < target
     * - (3, 5) ，3 < 5 且 nums[3] + nums[5] = -3 < target
     * - (4, 5) ，4 < 5 且 nums[4] + nums[5] = -8 < target
     * - (4, 6) ，4 < 6 且 nums[4] + nums[6] = -4 < target
     * \
     * @param args args
     */
    public static void main(String[] args) {
        CountPairs countPairs = new CountPairs();
        List<Integer> nums = new ArrayList<>();
        nums.add(-1);
        nums.add(1);
        nums.add(2);
        nums.add(3);
        nums.add(1);
        int target = 2;
        System.out.println(countPairs.countPairs2(nums, target));
    }

    /**
     * 计数对:双循环模拟
     *
     * @param nums   nums
     * @param target 目标
     * @return int
     */
    public int countPairs(List<Integer> nums, int target) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if(nums.get(i) + nums.get(j) < target){
                    ans++;
                }
            }
        }
        return ans;
    }

    /**
     * 计数对2
     * 数组计数
     * @param nums   nums
     * @param target 目标
     * @return int
     */
    public int countPairs2(List<Integer> nums, int target) {
        int i = 0;
        int j = nums.size() - 1;
        int res = 0;
        List<Integer> collect = nums.stream().sorted().collect(Collectors.toList());
        for(;i < j; ){
            //如果判断式为false则说明改范围内的最小位+最大位数据都满足条件，直接累加即可。同时最小位增加看新范围内是否满足条件
            if(collect.get(i) + collect.get(j) >= target){
                j--;
            }else{
                res += j-i;
                i++;
            }
        }
        return res;
    }

}
